package com.gitee.feizns.explore.data_structure.graph;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * 面试题 04.01. 节点间通路
 * @author feizns
 * @since 2020/3/24
 */
public class FindWhetherExistsPath {


    //12
    //[[0, 1], [1, 2], [1, 3], [1, 10], [1, 11], [1, 4], [2, 4], [2, 6], [2, 9], [2, 10], [2, 4], [2, 5], [2, 10], [3, 7], [3, 7], [4, 5], [4, 11], [4, 11], [4, 10], [5, 7], [5, 10], [6, 8], [7, 11], [8, 10]]
    //2
    //3
    static int[][] graph = new int[][]{{0, 1}, {1, 2}, {1, 3}, {1, 10}, {1, 11}, {1, 4}, {2, 4}, {2, 6}, {2, 9}, {2, 10}, {2, 4}, {2, 5}, {2, 10}, {3, 7}, {3, 7}, {4, 5}, {4, 11}, {4, 11}, {4, 10}, {5, 7}, {5, 10}, {6, 8}, {7, 11}, {8, 10}};

    static Graph g;

    public static void main(String[] args) {
        System.out.println(findWhetherExistsPath(12, graph, 2, 3));
    }

    public static boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        g = create(n, graph);
        return dfs(start, target);
    }

    private static boolean dfs(int curt, int target) {
        if ( curt != target ) {
            Set<Integer> adj = g.adj(curt);
            if ( !adj.isEmpty() ) {
                for (Integer v : adj) {
                    if ( dfs(v, target) )
                        return true;
                }
            }
            return false;
        }
        return true;
    }

    private static Graph create(int n, int[][] graph) {
        Graph ret = new Graph(n);
        for (int[] ints : graph) {
            ret.add(ints[0], ints[1]);
        }
        return ret;
    }

    private static class Graph {

        private Set<Integer>[] sets;

        public Graph(int size) {
            sets = new HashSet[size];
            for (int i = 0; i < sets.length; i++) {
                sets[i] = new HashSet<>();
            }
        }

        public void add(int s, int t) {
            sets[s].add(t);
        }

        public Set<Integer> adj(int s) {
            return sets[s];
        }

    }

}
